<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>



  
  
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">


  


  
  
  
  <title>Safe Ownership-Based Memory Management</title>
  <meta content="Adam Dingle" name="author">



  
  
  <style type="text/css">
h1 { font-size: 18pt;
font-weight: bold;
font-family: Arial,Helvetica,sans-serif;
text-align: center;
}
.author { font-family: Arial,Helvetica,sans-serif;
font-size: 12pt;
text-align: center;
}
address { text-align: center;
font-family: Arial,Helvetica,sans-serif;
font-size: 10pt;
font-style: normal;
}
body {
font-size: 9pt;
}
h2 { font-family: Times New Roman,Times,serif;
font-size: 12pt;
font-weight: bold;
}
h3 { font-family: Times New Roman,Times,serif;
font-size: 12pt;
font-weight: bold;
}
h4 { font-family: Times New Roman,Times,serif;
font-size: 11pt;
font-style: italic;
font-weight: normal;
}
  </style>
</head>


<body>

<h2>RELATED WORK</h2>


<p>Our work represents one of many attempts to find a "sweet spot" in the
trade-off space between fully manual and fully automatic memory management
(that is, garbage collection).  There are many inter-related issues, chief
among them being memory footprint, run-time cost, determinism, and ease of
programming.  We compare our work to that of others across these various axes.</p>

<p>Region-based memory management provides bulk-freeing of objects,
often based on a stack discipline.  Regions generally provide low cost and good
determinism, but if provided in a safe manner either require either burdensome
annotation [Tofte type 1] or an analysis which is frequently over-conservative
[Tofte type 2].  Region systems that follow a stack discipline often suffer
from large numbers of object being assigned (by analysis or by the programmer)
to the global region which is never collected (or must be collected by a
supplementary garbage collector).  </p>

<p>The Real-time Specification for Java (RTSJ) [Bollella'00] provides a
stack-oriented region-based memory management based on Scopes.  Scopes have
neither annotations nor automatic inference; instead it is the responsibility
of the programmer to allocate objects in the correct scope.  Storing a pointer
that violates the stack discipline of scopes causes a run-time exception.
Scopes are thus type-safe but subject to run-time exceptions that are difficult
to prevent and are highly dependent on interactions between different
components.  In addition, it is often either convenient or necessary to place
objects in the outermost scope (called Immortal memory), in particular when it
is necessary to share objects between scope-managed and garbage-collected
memory.  </p>

<p>The goals of the Cyclone language [Hicks et al'04] are probably most similar to
those of Gel; its goal is to provide a safe alternative to C for systems
programming.  Cyclone provides several forms of safe memory management:
regions, unique pointers, and reference counting.  Cyclone's regions require
explicit annotations in the source code, and can be both lexically scoped (in
the style of [Tofte 1]) or dynamically scoped.  In the latter case, if a region
is freed dynamically subsequent attempts to access objects in that region will
generate a run-time exception.</p>

<p>Cyclone's unique pointers are based on linear types [cite] and are
essentially like Gel's owning pointers, but without the capability to reference
count non-owning references.  Some polymorphism across memory management styles
is provided by allowing sets of unique pointers to be temporarily treated as
though they belong to a region.  Cyclone also provides explicit (but safe)
reference counting; reference counted objects are treated as belonging to a
special region called RC.</p>

<p>The experience of the language designers in writing the Cyclone compiler is
instructive: first coarse-grained regions were used, which reduced the
annotation burden.  However, coarse regions did not free memory soon enough and
led to excessive space consumption.  The compiler was then re-written using
fine-grained regions, at which point the annotations became overly cumbersome.
Eventually the compiler was re-written to use garbage collection [Morrisett '05].</p>

<p>The design goals of our system are loosely similar to those of
systems using
<dfn>region-based memory management</dfn> [Henglein, 2005];
such systems may also free memory without using explicit deallocation
or a garbage collector.&nbsp; But our mechanism is fairly different
in that it allocates and deallocates objects individually and frees
objects soon after they are no longer needed.&nbsp; The type
annotations in our system are also much simpler than those in many
region-based systems.<br>

<p>Ownership types have received considerable attention in recent years.  Unlike
Gel's concept of ownership, these approaches rely entirely on the type system
[Boyapati, Boyland].  Ownership is used for a variety of purposes: modularity
[Clarke et al'01], improved alias analysis and optimization [..],
thread-locality [..], and real-time memory management [Boyapati et al -
PLDI'03; Zhao et al'04].  Generally speaking, these approaches have a high
annotation overhead and/or require significant redundant code due.

<!-- Corsaro and Cytron.  MSR system that has owned pointer regions.  Gay -->

<p>Real-time garbage collection [Bacon et al, POPL'03; Henriksson PhD] provides
overall timing determinism and ease of programming, but suffers from the memory
overhead issues associated with garbage collection in general, and does not
provide determinism in terms of the times at which individual objects are
freed.  Also, during garbage collection some fraction of the CPU time (on the
order of 30%) is unavailable to real-time tasks.</p>



<br>

</body>
</html>
